package leetcode.editor.vscdev;

import java.util.*;

import leetcode.editor.utils.TreeNode;

public class lc617 {
    class Solution {
        // 递归法
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            // 递归终止条件
            if (root1 == null && root2 == null) return null;
            // 创建新节点, 进行合并
            TreeNode root = new TreeNode();
            if (root1 != null && root2 != null) {
                root.val = root1.val + root2.val;
                root.left = mergeTrees(root1.left, root2.left);
                root.right = mergeTrees(root1.right, root2.right);
            } else if (root1 != null) {
                root.val = root1.val;
                root.left = mergeTrees(root1.left, null);
                root.right = mergeTrees(root1.right, null);
            } else {
                root.val = root2.val;
                root.left = mergeTrees(null, root2.left);
                root.right = mergeTrees(null, root2.right);
            }
            return root;
        }
        // 队列迭代
        public TreeNode mergeTrees1(TreeNode root1, TreeNode root2) {
            if (root1 == null) return root2;
            if (root2 == null) return root1;
            TreeNode root = new TreeNode(root1.val + root2.val);
            /* deque和queue的区别
             * deque是双端队列，可以添加和删除头尾元素
             * queue是队列，只能添加和删除尾元素
             */
            Deque<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                // TODO 合并二叉树迭代法未完成
            }
            return root;
        }
    }
}
